# -*- coding:utf-8 -*-
# @File       :   最大怒气值最小.py
# @Author     :   LINING
# @Time       :   2024/3/11 14:43
# @Description :
"""
https://www.luogu.com.cn/problem/P1525
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
"""

boxs = 2
infects = [[1,4,2534], [2,3,3512], [1, 2, 28351], [1, 3, 6618], [2, 4, 1805], [3, 4, 12884]]


def get_box(size, nums):
    """
    size: 最大怒气值
    nums:影响力
    """
    box = 1
    box_size = 0
    for i in nums:
        if box_size+i <= size:
            box_size = box_size+i
        else:
            box = box+1
            box_size = i
    return box


def get_min(infect, box):
    infect_list = [i[2] for i in infect]
    left = min(infect_list)
    right = sum(infect_list)
    while left < right:
        mid = int((left+right)/2)
        if get_box(mid, infect_list) <= box:
            right = mid
        else:
            left = mid+1
    return right


print(get_min(infects, boxs))

# 做错了





